
//977.有序数组的平方
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();

        int cur1=0;
        while(cur1<n&&nums[cur1]<0) cur1++;
        cur1--;  //cur1向前走   从[0,cur1]的平方是降序的
        int cur2=cur1+1;  //cur2向后走  从[cur2,n-1]的平方是升序的

        vector<int> ret(n);
        int k=0;
        while(cur1>=0&&cur2<n)
        {
            if(abs(nums[cur1])<abs(nums[cur2])) ret[k++]=nums[cur1]*nums[cur1--];
            else ret[k++]=nums[cur2]*nums[cur2++];
        }
        while(cur1>=0) ret[k++]=nums[cur1]*nums[cur1--];  //判断cur1是否走完了
        while(cur2<n) ret[k++]=nums[cur2]*nums[cur2++];
        
        return ret;
    }
};